package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/4 18:50
 */
public class J22 {


    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static ListNode getKthFromEnd(ListNode head, int k) {
        // 反转的到在, 在反转
        head = reverseList(head);
        ListNode ans = head;
        while (k > 1) {
            ans = ans.next;
            k--;
        }
        reverseList(head);
        return ans;
    }

    public static ListNode reverseList(ListNode head) {
        // 反转链表
        ListNode cur = head;
        ListNode pre = null;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }


    /** 双指针 */
    // 正着找到第k个, 然后继续和从头开始走former走到头,latter就是倒数第k个
    public ListNode getKthFromEnd2(ListNode head, int k) {
        ListNode former = head, latter = head;
        for(int i = 0; i < k; i++)
            former = former.next;
        while(former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }


    // for test
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);
        head.next.next.next.next.next.next = new ListNode(7);

        ListNode ans = getKthFromEnd(head, 3);
        System.out.println(ans.val);
    }

}
